|
In computer science, input enhancement is the principle that processing a given input to a problem and altering it in a specific way will increase runtime efficiency or space efficiency, or both. The altered input is usually stored and accessed to simplify the problem. This is done by exploiting the structure and properties of the inputs to create various speed-ups in the efficiency of the algorithm. == Presorting == Input enhancement when searching, or presorting, has been an essential component of the algorithm world for some time in computer science. The main idea behind this principle is that the efficiency of a search is much faster when the time is taken to sort a data structure before attempting to search for the element in said data structure. This is true because the addition of a sorting component to an algorithm is added to the runtime of the searching algorithm, not multiplied, and thus it only competes for the slowest portion of the algorithm. Since the efficiency of algorithms is measured by the slowest component, the addition of the sorting component is negligible if the search is less efficient. Unfortunately, presorting is usually the slowest component of the algorithm. Contrasting, a searching algorithm without a presort is almost always slower than that with a presort. The sorting portion of the algorithm processes the input of the problem before the searching portion of the algorithm is even reached. Having the elements of the input sorted in some sort of order makes the search trivial in practice. The simplest sorting algorithms – insertion sort, selection sort, and bubble sort – all have a worst case runtime of O(''n''2), while the more advanced sorting algorithms – heapsort, merge sort – which have a worst case runtime of O(''n'' log ''n'') – and quicksort – which has a worst case of O(''n''2) but is almost always O(''n'' log ''n''). Utilizing these sorting algorithms, a search algorithm that incorporates presorting will yield these big-O efficiencies. A simple example of the benefits of presorting can be seen with an algorithm that checks an array for unique elements: If an array of ''n'' elements is given, return true if every element in the array is unique, otherwise return false. The pseudocode is presented below: algorithm uniqueElementSearch(A()) for ''i'' = 0 to ''n'' – 1 do for ''j'' = ''i'' + 1 to ''n'' do if A() = A() return false return true Without a presort, at worst case, this algorithm would require every element to be checked against every other element with two possible outcomes: either there is no duplicate element in the array, or the last two elements in the array are the duplicates. This results in a O(''n''2) efficiency. Now compare this to a similar algorithm that utilizes presorting. This algorithm sorts the inputted array, and then checks each pair of elements for a duplicate. The pseudocode is presented below: algorithm presortUniqueElementSearch(A()) sort(A()) for ''i'' = 0 to ''n'' – 1 do if A() = A(+ 1 ) return false return true As previously stated, the least efficient part of this algorithm is the sorting of the array, which, if an efficient sort is selected, would run in O(''n'' log ''n''). But after the array is sorted, the array only needs to be traversed once, which would run in O(''n''). This results in a O(''n'' log ''n'') efficiency. This simple example demonstrates what is capable with an input enhancement technique such as presorting. The algorithm went from quadratic runtime to linearithmic runtime which will result in speed-ups for large inputs. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Input Enhancement (Computer Science)」の詳細全文を読む スポンサード リンク
|